#include<bits/stdc++.h>
using namespace std;
int n,a[100000],minn;
int num(int *c[]){
    int nu=0;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--){
            if(c[j]==c[i]){
                a[i]=a[j];
                nu+=a[i];
                break;
            }
        }
    }
    return nu;
}
void col(int *c[],int s){
    if(s==n){
        minn=min(minn,num(c));
        return;
    }
    for(int i=1;i<=2;i++){
        *c[s]=i;
        col(c,s+1);
    }
}
int main(){
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    int K;
    cin>>K;
    while(K--){
        int maxx=INT_MIN;
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        int *c[100000];
        memset(c,0,sizeof(c));
        minn=INT_MIN;
        col(c,0);
        cout<<minn;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
